1. Field of the Invention
This invention relates, generally, to cryptography. More particularly, it relates to a system and method of probabilistic password cracking.
2. Brief Description of the Prior Art
Human memorable passwords provide the basis for much of today's encryption and authentication protocols. This is due to numerous features that passwords possess, such as the lack of additional hardware requirements (e.g., scanners or public/private key tokens), user acceptance, and the ease with which passwords can be transformed into encryption keys via hashing.
In the setting of cracking passwords in a forensic setting, the attacker (e.g., law enforcement) has obtained the password hashes or encrypted files and is now attempting to decrypt the files by figuring out the original passwords from the hashes. A forensic, or offline password cracking attack can be broken up into three distinct steps. First, the attacker makes a guess as to the user's password, for example “password123”. Next, the attacker hashes that guess using whatever hashing algorithm was used. In the case of file encryption, the hashing algorithm is used to convert the password guess into an encryption key. Thirdly, the attacker compares the hash of the password guess to the hash the attacker is trying to crack. If the two hashes match, the password is considered broken. With file encryption, the attacker attempts to decrypt the file (or file header) with the key generated, and if the file is decrypted successfully, the password is considered cracked. These three steps are repeated over and over again with new guesses until the attacker breaks the password, or runs out of time. However, this process is very time-consuming (i.e., time that law enforcement might not have) and inefficient in making password guesses.
The two most commonly used methods to make password guesses are brute-force and dictionary based attacks. With brute-force, the attacker attempts to try all possible password combinations. While this attack is guaranteed to recover the password if the attacker manages to brute-force the entire password space, exhaustive search of the password space is often not feasible due to time and equipment constraints. Several techniques have been developed to generate more targeted search spaces, for example Markov models (L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” Proceedings of the IEEE, V. 77, No. 2 (February 1989)), and can be used to generate search spaces according to heuristics about the structure of likely passwords. This strategy has been indeed adopted by popular password crackers such as JOHN THE RIPPER™.
If no salting is used, brute-force attacks can be dramatically improved through the use of pre-computation and powerful time-memory trade-off techniques known as rainbow tables (N. Mentens, L. Batina, B. Preneel, I. Verbauwhede, “Time-Memory Trade-Off Attack on FPGA Platforms: UNIX Password Cracking,” Proceedings of the International Workshop on Reconfigurable Computing: Architectures and Applications, Lecture Notes in Computer Science, V. 3985, pg. 323-334, Springer (2006); M. Hellman, “A Cryptanalytic Time-Memory Trade-Off,” IEEE Transactions on information Theory, V. 26, Issue 4, pg. 401-406 (1980); P. Oechslin, “Making a Faster Cryptanalytic Time-Memory Trade-Off,” Proceedings of Advances in Cryptology (CRYPTO 2003), Lecture Notes in Computer Science, V. 2729, pg. 617-630, Springer (2003)). Some Markov models may be de-randomized into a deterministic index function, allowing them to be combined with time-memory trade-off techniques, such as the construction of optimized rainbow tables (A. Narayanan and V. Shmatikov, “Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff,” CCS '05 (Alexandria, Va. Nov. 7-11, 2005)).
The second main technique of making password guesses is a dictionary attack. The dictionary itself may be a collection of word lists that are believed to be common sources from which users choose mnemonic passwords. However, users rarely select unmodified elements from such lists, for instance because password creation policies prevent it, and instead generally modify the words in such a way that they can still recall them easily. In a dictionary attack, the attacker tries to reproduce this approach to password choice by processing words from an input dictionary and systematically producing variants through the application of pre-selected mangling rules. For example, a word-mangling rule that adds the number “9” at the end of a dictionary word would create the guess “password9” from the dictionary word “password.”
For a dictionary attack to be successful, it requires the original word to be in the attacker's input dictionary and for the attacker to use the correct word-mangling rule. While dictionary based attack is often faster than brute-force on average, attackers are still limited by the amount of word-mangling rules they can take advantage of due to time constraints. Such constraints become more acute as the sizes of the input dictionaries grow. In this case, it becomes important to select rules that provide a high degree of success while limiting the number of guesses required per dictionary word.
Choosing the right word-mangling rules is crucial as the application of each rule results in a large number of guesses. This is especially true when the rules are used in combination. For example, adding a specific two-digit number to the end of a dictionary word for a dictionary size of 800,000 words would result in 80,000,000 guesses. Creating a rule to allow the first letter to be uppercase or lowercase would double this figure. Furthermore, in a typical password retrieval attempt, it is necessary to try many different mangling rules. Issues arise as to which word-mangling rules should one try and in what order. This is obviously a resource-consuming process.
Attackers, such as law enforcement, are particularly limited by the amount of time and resources that can be devoted to a password cracking session. Even with the introduction of faster hardware implementations for password cracking software, such as GPU's, FPGA's, multi-core computers, and cell processors, the attacker is still limited by the corresponding defensive techniques now being employed. For example, while older password hashing algorithms such as NTLM only required the cracker to compute one round of the MD4 hashing algorithm to make a password guess, new encryption tools such as TRUECRYPT™ can require application of the SHA-512 hashing algorithm one-thousand times using the same guess. In addition, techniques like password salting can render hash pre-computation attacks such as rainbow tables completely ineffective. Thus, it is important for an attacker to make the best guesses possible to maximize the chances of cracking the password given time and equipment constraints.
In addition, there have been many studies that have explored how users choose passwords [S. Riley, “Password security: what users know and what they actually do,” Usability News, 8(1); B. Stone-Gross, M. Cova, L. Cavallaro, B. Gilbert, M. Szydlowski, R. Kemmerer, C. Kruegel, and G. Vigna, “Your botnet is my botnet: analysis of a botnet takeover,” Proceeding of the 16th ACM Conference on Computer and Communications Security, pp 635-647; R. Shay, S. Komanduri, P. G. Kelley, P. G. Leon, M. L. Mazurek, L. Bauer, N. Christin, and L. F. Cranor, “Encountering stronger password requirements: user attitudes and behaviors,” In 6th Symposium on Usable Privacy and Security, July 2010] and recent studies have turned to greater exploration of the strength of passwords [P. G. Kelley, S. Komanduri, M. L. Mazurek, R. Shay, T. Vidas, L. Bauer, N. Christin, L. F. Cranor, and J. Lopez, “Guess again (and again and again): measuring password strength by simulating password-cracking algorithms,” Proceedings of the 2012 IEEE Symposium on Security and Privacy, pp 523-537; S. Houshmand and S. Aggarwal, “Building better passwords using probabilistic techniques,” Proceedings of the 28th Annual Computer Security Applications Conference (ACSAC '12), December 2012, pp. 109-118; C. Castelluccia, M. Durmuth, D. Perito, “Adaptive password-strength meters from Markov models,” NDSS '12; S. Schechter. C. Herley, M. Mitzenmacher, “Popularity is everything: a new approach to protecting passwords from statistical-guessing attacks,” HotSec'10: Proceedings of the 5th USENIX conference on Hot Topics in Security]. However, there are not many studies that explore keyboard shapes and how often users choose keyboard combinations or that explore the strength of such keyboard patterns. For example, the focus of De Luca et al. [A. De Luca, R. Weiss, and H. Hussmann, “PassShape—stroke based shape passwords,” Proceedings of OzCHI 2007] is mainly on how to define such structures. De Luca et al. use directional line segments (of varying lengths) that they call a stroke and can thus describe a shape on a 10 digit PIN pad.
The work by Schweitzer et al. [D. Schweitzer. J. Boleng, C. Hughes, and L. Murphy, “Visualizing keyboard pattern password,” 6th International Workshop on Visualization for Cyber Security, 2009, pp 69-73] focuses on keyboard patterns and describes a way to pictorially describe a shape on the keyboard. Contiguous sequences of key strokes are easy to visualize but they have more difficulty with elements such as repeated strokes. In order to visualize this, they propose that each repeated stroke creates a petal on the same digit illustration. They do describe a small experiment in which they have 161 users create 250 unique patterns. This experiment is performed after the users were given a brief tutorial on how to create patterns. The top 11 shapes that were used for the passwords were then noted. In Schweitzer et al.'s work, they generate a number of keyboard patterns from these shapes and add these to a dictionary (a common way of using keyboard patterns). They then use this dictionary in cracking passwords and compare with John the Ripper. They obtained 11 supposedly strong passwords from their institution and were able to crack 2 of these. However, these keyboard shapes are not integrated into a context-free grammar that is used to create guesses and thus the guesses are incomplete and inefficient.
The work by Bonneau [J. Bonneau, “The science of guessing: analyzing an anonymized corpus of 70 million passwords,” In the 2012 IEEE Symposium on Security and Privacy, 2012, pp. 538-552] explores how users create passwords by investigating several revealed password sets, such as RockYou [A. Vance, “If your password is 123456, just make it hackme,” New York Times, January 2010] and CSDN [Bernd Chang, “6 Million User Data of China Software Developer Network (CSDN) Leaked”, HUG China, Dec. 22, 2011](a Chinese set) and describes how many passwords have various characteristics such as all digits, non-ASCII characters and use of adjacent keys. They use a pattern of adjacent keys excluding repeats as an indication of a keyboard pattern and found that 3% of passwords in RockYou and 11% of CSDN had this pattern. However, this work cannot be directly applied to developing better techniques for probabilistic password cracking.
There has been a great deal of work focused on passphrases including their resistance to cracking and their memorability. For example, Yan et al. [Jeff Yan, Alan Blackwell, Ross Anderson, and Alasdair Grant, “Password Memorability and Security: Empirical Results,” IEEE Security and Privacy Magazine, 2(5):25, 2004] conducted an experiment on phrases that are used in deriving mnemonic passwords (using the initial letters of each word in the phrase as the password). They found that such passwords had good security and memorability. As a counterpoint, Kuo et al. [Kuo, C., Romanosky, S., and Cranor, L. F., “Human Selection of Mnemonic Phrase-based Passwords,” Symp. on Usable Privacy and Security (SOUPS), 2006] found that users tend to use common phrases and thus the security might not be as high as expected. In more recent work, Bonneau and Shutova [Joseph Bonneau, and Ekaterina Shutova, “Linguistic properties of multi-word passphrases,” FC'12, Proceedings of the 16th international conference on Financial Cryptography and Data Security, 2010, PP. 1-12] discuss two word sequences (bigrams) and develop models to indicate which are more likely to represent user behavior in creating these bigrams. They find that users tend to choose natural patterns over other possible patterns such as randomly choosing two words. Furthermore, by trying to guess a corpus of passphrases from AMAZON, they conclude that the security of passphrases is higher than that of passwords. However, this work focuses on passphrases (all words) rather than trying to learn to what extent multi-words are used as components of passwords in order to develop better probabilistic context-free grammars that could create the appropriate guesses incorporating multi-word patterns.
In the literature related to analyzing dictionaries, the dictionaries are sometimes viewed as the guesses themselves. In Bonneau [J. Bonneau, “The science of guessing: analyzing an anonymized corpus of 70 million passwords,” In the 2012 IEEE Symposium on Security and Privacy, 2012, pp. 538-552], the author creates dictionaries for different groups of YAHOO users based on linguistic background and defines a dictionary as the top one thousand actual passwords from that group. The effectiveness of such dictionaries against other linguistic groups (e.g., Chinese against Italian) is determined. However, this work is really analyzing a set of guesses and not the effectiveness of a dictionary as may be used by a probabilistic password cracking system for generating guesses.
In many other studies, dictionaries are used both as a source of passwords as well as a source for generating variant guesses by applying mangling rules. For example, Klein [D. V. Klein, “Foiling the cracker: a survey of and improvements to password security,” Proceedings of USENIX UNIX Security Workshop, 1990] describes some early work in this area. Dell'Amico et al. [M. Dell'Amico, P. Michiardi and Y. Roudier, “Password strength: an empirical analysis,” Proceedings of IEEE INFOCOM 2010] can be considered representative of recent work in this area. This study considers several dictionaries available from John the Ripper and an evaluation is done by first comparing the passwords cracked using the dictionary entries only. Two results emerge: (1) it is better to use the same type of dictionary as the target type (for example, Finnish dictionary when attacking Finnish passwords), (2) and although larger dictionaries are better, there are diminishing returns when using these larger dictionaries. The authors next indicate that this also holds true when using dictionaries that are used in conjunction with mangling rules wherein they consider the full space of guesses based on the mangling rules. However, this work does not consider the effectiveness of different dictionaries as the probabilistic password cracking system generates more and more guesses.
All referenced patents and publications are incorporated herein by reference in their entirety. Furthermore, where a definition or use of a term in a reference, which is incorporated by reference herein, is inconsistent or contrary to the definition of that term provided herein, the definition of that term provided herein applies and the definition of that term in the reference does not apply.
Accordingly, what is needed is a probabilistic password cracking system and method that maximizes the chances of cracking a password using keyboard patterns and multiple dictionaries. However, in view of the art considered as a whole at the time the present invention was made, it was not obvious to those of ordinary skill in the field of this invention how the shortcomings of the prior art could be overcome.
While certain aspects of conventional technologies have been discussed to facilitate disclosure of the invention, Applicants in no way disclaim these technical aspects, and it is contemplated that the claimed invention may encompass one or more of the conventional technical aspects discussed herein.
The present invention may address one or more of the problems and deficiencies of the prior art discussed above. However, it is contemplated that the invention may prove useful in addressing other problems and deficiencies in a number of technical areas. Therefore, the claimed invention should not necessarily be construed as limited to addressing any of the particular problems or deficiencies discussed herein.
In this specification, where a document, act or item of knowledge is referred to or discussed, this reference or discussion is not an admission that the document, act or item of knowledge or any combination thereof was at the priority date, publicly available, known to the public, part of common general knowledge, or otherwise constitutes prior art under the applicable statutory provisions; or is known to be relevant to an attempt to solve any problem with which this specification is concerned.